package org.kk.a.sort;
import static org.kk.util.Tool.*;
public class MergerSort {
    public static void main(String[] args) {
        //int[] arr = {1,2,3,6,2,4,8};
        int[] arr = {10,1,7,6,2,5,9,8,4,3};
        sort(arr);
        print(arr);
    }
    public static void sort(int[] arr){
        merge(arr, 0, arr.length -1);
    }

    private static void merge(int[] arr, int left, int right) {
        int mid = (left + right) >> 1;
        if(left < right){
            merge(arr,left, mid);
            merge(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    private static void merge(int[] arr, int left,int mid, int right){
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while(i <= mid && j <= right){
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while(i <= mid){
            temp[k++] = arr[i++];
        }
        while(j <= right){
            temp[k++] = arr[j++];
        }
        for(int k2 = 0; k2 < temp.length; k2++){
            arr[k2 + left] = temp[k2];
        }
    }
}
